|
The Misra & Gries edge coloring algorithm is a polynomial time algorithm in graph theory that finds an edge coloring of any graph. The coloring produces uses at most colors, where is the maximum degree of the graph. This is optimal for some graphs, and by Vizing's theorem it uses at most one color more than the optimal for all others. It was first published by Jayadev Misra and David Gries in 1992. It is a simplification of a prior algorithm by Béla Bollobás. This algorithm is the fastest known almost-optimal algorithm for edge coloring, executing in time. A faster time bound of was claimed in a 1985 technical report by Gabow et al., but this has never been published. In general, optimal edge coloring is NP-complete, so it is very unlikely that a polynomial time algorithm exists. There are however exponential time exact edge coloring algorithms that give an optimal solution. ==Fans== A color ''x'' is said to be free of an edge (''u,v'') on ''u'' if ''c(u,z)'' ≠ ''x'' for all (u,z) E(G) : ''z≠v''. A fan of a vertex u is a sequence of vertices F() that satisfies the following conditions: #F() is a non-empty sequence of distinct neighbors of u #(F(),u) E(G) is uncolored #The color of (F(),u) is free on F() for 1 ≤ i < k Given a fan F, any edge (F(), X) for 1 ≤ i ≤ k is a fan edge. Let c and d be colors. A cdX-path is an edge path that goes through vertex X, only contains edges colored c and d and is maximal (we cannot add any other edge as it would include edges with a color not in ). Note that only one such path exists for a vertex X, as at most one edge of each color can be adjacent to a given vertex. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Misra & Gries edge coloring algorithm」の詳細全文を読む スポンサード リンク
|